位运算的一些用例

发表于 | 分类于 | 阅读次数

位运算

几乎每种编程语言都为我们提供一种运算，它直接操作二进制数据，这种运算叫做位运算。

位运算分为移位、取反、与、或、异或、非，其中移位又包括左移位、右移位、左无符号移位、右无符号移位。

含义 Java写法
与 a & b
或 a \ b
异或 a ^ b
非（取反） ~a
左移 a<<b
右移 a>>b
无符号左移 a <<< b
无符号右移 a>>>b

可能大多数时候觉得，这些位运算除了平时刷题用到，好像并没有什么用。当时当我们去看一些源代码的时候，比如JDK、Android SDK等源代码的时候，我们会发现有很多地方都会看见一些位运算的影子。这些使用位运算的例子都会有某个命令为mask的变量，这个mask就是用来存储某几种状态的信息。

那么什么是位掩码呢？根据维基百科的定义：

In computer science, a mask is data that is used for bitwise operations, particularly in a bit field.

位掩码是一种用来方便进行位运算的数据，可以帮助我们在读取或者修改某个特定的位上的值，而不会修改其他位的值。

位运算的用例一—权限控制

假设有这么一个场景，需要对某个文件设置权限，假设有三种权限需要设置：读、写、执行。那么通常的做法可能就是采用三个布尔值来存储当前的权限。
那么写法通常可能是这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public class Permission {
    private boolean is_allowed_read = false;
    private boolean is_allowed_write = false;
    private boolean is_allowed_execution = false;
    
    public Permission() {
    
    }
    
    public Permission(boolean is_allowed_read, boolean is_allowed_write, boolean is_allowed_execution) {
        this.is_allowed_read = is_allowed_read;
        this.is_allowed_write = is_allowed_write;
        this.is_allowed_execution = is_allowed_execution;
    }
    
    public void setIsAllowedRead(boolean is_allowed_read) {
      this.is_allowed_read = is_allowed_read;
    }
    
    public boolean getIsAllowedRead() {
      return this.is_allowed_read;
    }
    
    public void setIsAllowedWrite(boolean is_allowed_write) {
      this.is_allowed_write = is_allowed_write;
    }
    
    public boolean getIsAllowedWrite() {
      return this.is_allowed_write;
    }
    
    public void setIsAllowedExecution(boolean is_allowed_execution) {
      this.is_allowed_execution = is_allowed_execution;
    }
    
    public boolean getIsAllowedExecution() {
      return this.is_allowed_execution;
    }
}

上面这种写法可能是比较常见的，比较符合我们的思维习惯，但是使用位运算中掩码的概念来改写这个例子，会使得更加简洁、高效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public class Permission {
    private final static byte Allowe_Read = 1 << 0;//00000001
    private final static byte Allowe_Write = 1 << 1;//00000010
    private final static byte Allow_Execution = 1 << 2;//00000100
    
    private byte permissionMask = 0x00;//默认没有任何权限
    
    public Permission() {
    
    }
    
    public Permission(byte permission) {
        this.permissionMask = permission;
    }
    
    //增加一项或者多项权限
    public void enable(byte permission) {
         this.permissionMask |= permission;
    }
    
    //禁用一项或多项的权限
    public void disable(byte permission) {
        this.permissionMask &= ~permission;
    }
    
    //查询一项或多项权限是否被启用
    public boolean isAllowed(byte permission) {
        return this.permissionMask & permission == permission;
    }
    
    
    //查询一项或多项权限是否被禁用
    public boolean isDisAllowed(byte permission) {
      return this.permissionMask & permission == 0;
    }
}

这种写法明显表达的信息量要多于第一种写法，举个例子：现在要同时启用三种权限，那么第一种写法就是：

1
2
3
4
5
6

setIsAllowedRead(true);

setIsAllowedWrite(true);

setIsAllowedExecution(true);

而第二种写法就是：

1
2

enable(Permission.ALLOW_READ | Permission.ALLOW_WRITE | Permission.ALLOW_EXECUTION);

这种写法对于使用Permission类的时候来说，方便许多。在Linux系统中设置权限时通常会用到

1
chmod 777 file

其中777就是1111111 | 1111111 | 1111111，可见Linux里面也是采用位运算中的掩码来设置文件权限的。

用位运算的方式来实现这个权限控制的优点是：高效，位运算比较接近与机器的运算方式；简洁，无论试编写还是使用都比较方便简洁。
缺点：代码不够直观，可读性差，当维护这段代码的时候可能比较恼火， 不如第一种写法一目了然。

通常如果需要维护n个开关变量（二值变量）的时候，只需要n位二进制的整数和数个mask即可，完成状态的保存和查询。这种写法在Android SDK里面是非常常见的。
可以加以推广，如果需要保存n个具有m种状态的变量，那么需要一个n位m进制的数即可完成。